#include "AIPathFinder.h"
#include <cmath>

AIPathFinder::AIPathFinder(int player, Board* board)
:playerID(player),gameBoard(board)
{
	secondaryPlayerID = (playerID == CHECKERS_PLAYER1?CHECKERS_PLAYER1_KING:CHECKERS_PLAYER2_KING);

	// Find all spots for this user
	for( int yPos=0; yPos < BOARD_Y; yPos++)
	{
		for( int xPos=0; xPos < BOARD_X; xPos++)
		{
			int boardValue =  gameBoard.GetValue(xPos,yPos);

			// All single or king'd pieces for this user
			if( playerID == boardValue ||
				secondaryPlayerID == boardValue)
			{
				Path* path = new Path();
				path->SetPieceAndPosition(xPos,yPos,boardValue);
				moves.push_back(path);
			}
		}
	}

	FindPaths();
}

AIPathFinder::~AIPathFinder(void)
{
	for( size_t i = 0; i < moves.size(); i++)
	{
		Path* md = dynamic_cast<Path*>(moves[i]);
		if( md != 0 )
		{
			delete md;
		}
	}

	moves.clear();
}

void AIPathFinder::FindPaths()
{
	// For each piece, see if there is a valid move somewhere and create a new path
	size_t maxSizeMoves = moves.size();
	vector<size_t> removedPieces;

	for( size_t i = 0; i < maxSizeMoves; i++)
	{
		// After this, nothing that didn't have a move or a jump is valid
		removedPieces.push_back(i);

		Path* md = dynamic_cast<Path*>(moves[i]);
		if( md != 0 )
		{
			vector<PiecePosition*> newPaths;

			GetMoveList(md,newPaths);
			GetJumpList(md,newPaths);
			if( newPaths.size() > 0 )
			{
				// Add to vector
				for( size_t newPathIdx = 0; newPathIdx < newPaths.size(); newPathIdx++)
				{
					Path* newPath = new Path(md);
					PiecePosition* newPosition = dynamic_cast<PiecePosition*>(newPaths[newPathIdx]);
					newPath->AddPathPoint(newPosition->GetX(), newPosition->GetY());

					if( abs(newPosition->GetX() - newPath->GetPosition().GetX()) > 1)
						newPath->SetJumpStatus(true);

					moves.push_back(newPath);

					// clean up memory
					delete newPosition;
				}
			}
			// clean up memory
			delete md;
		}
	}

	//clean up
	for( size_t idxRemove = 0; idxRemove < removedPieces.size(); idxRemove++)
	{
		moves.erase(moves.begin());
	}
	removedPieces.clear();

	// At this point we have a list of the moves and jumps, jumps started anyway, now we have to flush
	// out the remainder of the jumps to see if they can continue. Danger here is to make sure that a 
	// place jumped to doesn't circle back to the path it came from.....that will cause endless cylces.
CONTINUE_EXPAND:
	bool expandedJumps = false;
	maxSizeMoves = moves.size();
	for( size_t i = 0; i < maxSizeMoves; i++)
	{
		Path* md = dynamic_cast<Path*>(moves[i]);
		if( md != 0 && 
			md->GetJumpStatus())
		{
			// Have to see if we can expand this again.
			vector<PiecePosition*> newPaths;
			Path tmpPath;
			tmpPath.SetPieceAndPosition(md->GetPath()[md->GetPath().size()-1]->GetX(),
										md->GetPath()[md->GetPath().size()-1]->GetY(),
										md->GetPiece());

			GetJumpList(&tmpPath,newPaths);

			if( newPaths.size() > 0 )
			{
				for( size_t newPathIdx = 0; newPathIdx < newPaths.size(); newPathIdx++)
				{
					// Make sure it's not already in the path (can happen with kings only)
					bool exists = false;
					PiecePosition* newPosition = dynamic_cast<PiecePosition*>(newPaths[newPathIdx]);
					for( size_t existingPathIdx = 0; existingPathIdx < md->GetPath().size() ; existingPathIdx++)
					{
						PiecePosition* embedded = dynamic_cast<PiecePosition*>(md->GetPath()[existingPathIdx]);
						if( (*embedded) == (*newPosition))
						{
							exists = true;
							break;
						}
					}

					// If it's not already there, go ahead and add it in....
					if( !exists )
					{
						expandedJumps = true;
						Path* newPath = new Path(md);
						newPath->AddPathPoint(newPosition->GetX(), newPosition->GetY());
						newPath->SetJumpStatus(true);

						moves.push_back(newPath);
						// clean up memory
						removedPieces.push_back(i);
						//delete md;
					}

					// clean up memory
					delete newPosition;
				}
			}
		}
	}

	//clean up - sometimes we get two moves from a single position so we have to make sure we delete it
	// only once
	if( removedPieces.size() > 0)
	{
		size_t currentDeletedCount = 0;
		size_t deleteCount = removedPieces.size();
		int* deleted = new int[deleteCount];

		for( size_t idxRemove = 0; idxRemove < deleteCount; idxRemove++)
		{
			int deleteIndex = (int)removedPieces[idxRemove];

			bool alreadyDeleted = false;
			for( size_t startDelete = 0; startDelete < currentDeletedCount; startDelete++)
			{
				if( deleted[startDelete] == deleteIndex)
				{
					alreadyDeleted = true;
					break;
				}
			}

			if( !alreadyDeleted )
			{
				deleted[currentDeletedCount++] = deleteIndex;
				Path* md = dynamic_cast<Path*>(moves[deleteIndex ]);
				delete md;
				moves.erase(moves.begin() + deleteIndex );
			}
		}

		delete [] deleted;
		removedPieces.clear();
	}
	// If we expanded ANY jumps this round, go again to make sure we have complete expansion
	if( expandedJumps)
		goto CONTINUE_EXPAND;

	// Finally sort on priority
	SortMovesOnPriority();
}

void AIPathFinder::GetJumpList(Path* startingPoint, vector<PiecePosition*> &newPaths)
{
	PiecePosition position = startingPoint->GetPosition();
	int pieceType = startingPoint->GetPiece();
	int xPos = position.GetX();
	int yPos = position.GetY();

	// Jumps
	if( MoveAllowed(pieceType, xPos, yPos, xPos+2,yPos+2))
	{
		newPaths.push_back(new PiecePosition(xPos+2,yPos+2));
	}

	if( MoveAllowed(pieceType, xPos, yPos, xPos-2,yPos+2))
	{
		newPaths.push_back(new PiecePosition(xPos-2,yPos+2));
	}

	if( MoveAllowed(pieceType, xPos, yPos, xPos+2,yPos-2))
	{
		newPaths.push_back(new PiecePosition(xPos+2,yPos-2));
	}

	if( MoveAllowed(pieceType, xPos, yPos, xPos-2,yPos-2))
	{
		newPaths.push_back(new PiecePosition(xPos-2,yPos-2));
	}
}

void AIPathFinder::GetMoveList(Path* startingPoint, vector<PiecePosition*> &newPaths)
{
	PiecePosition position = startingPoint->GetPosition();
	int pieceType = startingPoint->GetPiece();
	int xPos = position.GetX();
	int yPos = position.GetY();

	// Check for moves, then check for jumps
	if( MoveAllowed(pieceType, xPos, yPos, xPos+1,yPos+1))
	{
		newPaths.push_back(new PiecePosition(xPos+1,yPos+1));
	}

	if( MoveAllowed(pieceType, xPos, yPos, xPos-1,yPos+1))
	{
		newPaths.push_back(new PiecePosition(xPos-1,yPos+1));
	}

	if( MoveAllowed(pieceType, xPos, yPos, xPos+1,yPos-1))
	{
		newPaths.push_back(new PiecePosition(xPos+1,yPos-1));
	}

	if( MoveAllowed(pieceType, xPos, yPos, xPos-1,yPos-1))
	{
		newPaths.push_back(new PiecePosition(xPos-1,yPos-1));
	}
}

bool AIPathFinder::MoveAllowed(int pieceType, int x1, int y1, int x2, int y2)
{
	if( x1 < 0 || 
		x2 < 0 ||
		x1 > (BOARD_X -1) ||  
		x1 > (BOARD_X -1) ||
		y1 < 0 || 
		y2 < 0 ||
		y1 > (BOARD_Y-1) || 
		y2 > (BOARD_Y-1) ||
		!VerifyDirection(pieceType,y1,y2) ||
		gameBoard.GetValue(x2,y2) != CHECKERS_EMPTY)
	{
		return false;
	}
	else if( abs(x2-x1) > 1)
	{	
		int jumpTarget = gameBoard.GetValue((x1+x2)/2,(y1+y2)/2);
		if( jumpTarget == playerID || 
			jumpTarget == secondaryPlayerID ||
			jumpTarget == CHECKERS_EMPTY)
		{
			return false;
		}
	}
	return true;
}

bool AIPathFinder::VerifyDirection(int pieceType, int y1, int y2)
{
	if( pieceType == CHECKERS_PLAYER1)
	{
		if( y2 >= y1 )
			return false;
	}
	else if( pieceType == CHECKERS_PLAYER2)
	{
		if( y2 <= y1 )
			return false;
	}
	return true;
}

void AIPathFinder::SortMovesOnPriority()
{
	for( size_t inner = 0; inner < moves.size(); inner++)
	{
		for( size_t outer = inner+1; outer < moves.size(); outer++)
		{
			Path* innerPath = dynamic_cast<Path*>(moves[inner]);
			Path* outerPath = dynamic_cast<Path*>(moves[outer]);

			if( outerPath->GetPriority() > innerPath->GetPriority())
			{
				Path* tmp = dynamic_cast<Path*>(moves[inner]);
				moves[inner] = moves[outer];
				moves[outer] = tmp;
			}
		}
	}
}

